/*
 * @Description: 
 * @FilePath: /Area-cpp/src/calculator.cpp
 * @Author: Wei Zhou
 * @Github: https://github.com/muyi2414
 * @Date: 2018-09-20 19:47:33
 * @LastEditors: Wei Zhou
 * @LastEditTime: 2020-02-28 20:13:48
 * @Copyright: Copyright © 2017 muyiro. All rights reserved.
 */

#include <iostream>
#include <stdio.h>
#include <stdint.h>
#include <stack>    //使用标准库里面的栈
#include <cstring>
#include <cctype>
#include <climits>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdlib>
#include <deque>
#include "calculator.h"

#define TEST

#define DEBUG       "[", __func__, " ", __LINE__, "] "

#define OPLEN_MAX   (8)
#define PO_FLOAT    (1e6)

#define MYERROR     (-1)

#define PI          (3.14159265358979)
#define E           (2.718281828459)

#if __cplusplus < 201703L
    #if __cplusplus < 201103L
    #error should use C++ 11 implementation
    #endif

    template<typename T>
    void println(T t) {
        std::cout << t << std::endl;
    }

    template<typename T, typename ...U>
    void println(T t, U... u) {
        std::cout << t;
        println(u...);
    }
#else
    template<typename ...U>
    void println(U... u) {
        size_t i = 0; ((std::cout << (i == 0 ? DEBUG : "") << u << (++i < sizeof...(u) ? ", " : "\n")), ...);
    }
#endif

/******************************************************************************
    Calculator::impl::impl
******************************************************************************/

typedef enum
{
    eOperation_invalid,
    eOperation_numInt,
    eOperation_numDouble,
    eOperation_op,
    eOperation_func,
} eOperationType;

struct
{
    eOperationType type;
    const char *name;
} g_operation[] =
{
    { eOperation_invalid,   "invalud"},
    { eOperation_numInt,    "numInt" },
    { eOperation_numDouble, "numDouble" },
    { eOperation_op,        "op" },
    { eOperation_func,      "func" },
};

typedef enum
{
    eFunction_invalid,
    eFunction_sqrt,
    eFunction_sin,
    eFunction_cos,
    eFunction_tan,
    eFunction_sinh,
    eFunction_cosh,
    eFunction_tanh,
    eFunction_arcsin,
    eFunction_arccos,
    eFunction_arctan,
    eFunction_fabs,
    eFunction_ln,
    eFunction_log,
} eFunctionType;

struct
{
    eFunctionType type;
    const char *name;
} g_function[] =
{
    { eFunction_invalid, "invalud"},
    { eFunction_sqrt,   "sqrt" },
    { eFunction_sin,    "sin" },
    { eFunction_cos,    "cos" },
    { eFunction_tan,    "tan" },
    { eFunction_sinh,   "sinh" },
    { eFunction_cosh,   "cosh" },
    { eFunction_tanh,   "tanh" },
    { eFunction_arcsin, "arcsin" },
    { eFunction_arccos, "arccos" },
    { eFunction_arctan, "arctan" },
    { eFunction_fabs,   "fabs" },
    { eFunction_ln,     "ln" },
    { eFunction_log,    "log" },
};

struct sOperation
{
    eOperationType  opType;     /* operation type */
    int             numInt;     /* valid when opType == eOperation_numInt */
    double          numDouble;  /* valid when opType == eOperation_numDouble */
    char            op;         /* valid when opType == eOperation_op */
    eFunctionType   funcType;   /* valid when opType == eOperation_func */

    void print(void)
    {
        switch(opType)
        {
            case eOperation_numInt:     println("{", g_operation[opType].name, ",", numInt, "}"); break;
            case eOperation_numDouble:  println("{", g_operation[opType].name, ",", numDouble, "}"); break;
            case eOperation_op:         println("{", g_operation[opType].name, ",", op, "}"); break;
            case eOperation_func:       println("{", g_operation[opType].name, ",", g_function[funcType].name, "}"); break;
        }
    }

    friend std::ostream& operator<<(std::ostream& os, sOperation& op);
};

std::ostream& operator<<(std::ostream& os, sOperation& op)
{
    switch(op.opType)
    {
        case eOperation_numInt:     os << op.numInt; break;
        case eOperation_numDouble:  os << op.numDouble; break;
        case eOperation_op:         os << op.op; break;
        case eOperation_func:       os << g_function[op.funcType].name; break;
    }
    return os;
}

template<typename T>
std::ostream& operator<<(std::ostream& os, std::deque<T>& op)
{
    for (typename std::deque<T>::iterator it = op.begin(); it != op.end(); it++) {
        os << *it << " ";
    }
    return os;
}

/******************************************************************************
    Calculator::impl::impl
******************************************************************************/
class Calculator::impl
{
public:
    impl(): 
        _flagLastIsNumber(false),
        _lastValue(0)
    {

    }

    void clear(void)
    {
        _flagLastIsNumber = false;
        _lastValue = 0;
        _strFormula.clear();
        _buffer.clear();
        _suffix.clear();
        _stack.clear();
        _value.clear();
    }

    void setFormula(std::string &str)
    {
        clear();
        _strFormula = str;
    }

    bool count(double &result)
    {
        sOperation op;
        double op1 = 0.0;
        double op2 = 0.0;
        double lfResult = 0;
        long ldResult = 0;

        convertFormula2Buffer();
        printDeque("convertFormula2Buffer");
        convertBuffer2Suffix();
        printDeque("convertBuffer2Suffix");

        while (!_suffix.empty())
        {
            op = _suffix.front();
            _suffix.pop_front();

            #ifdef TEST
            op.print();
            #endif

            switch (op.opType)
            {
                case eOperation_numInt:         pushToValue((double)op.numInt); break;
                case eOperation_numDouble:      pushToValue(op.numDouble); break;
                case eOperation_func:
                    switch (op.funcType)
                    {
                        case eFunction_sqrt:    pushToValue(sqrt(popFromValue())); break;
                        case eFunction_sin:     pushToValue(sin(popFromValue())); break;
                        case eFunction_cos:     pushToValue(cos(popFromValue())); break;
                        case eFunction_tan:     pushToValue(tan(popFromValue())); break;
                        case eFunction_sinh:    pushToValue(sinh(popFromValue())); break;
                        case eFunction_cosh:    pushToValue(cosh(popFromValue())); break;
                        case eFunction_tanh:    pushToValue(tanh(popFromValue())); break;
                        case eFunction_arcsin:  pushToValue(asin(popFromValue())); break;
                        case eFunction_arccos:  pushToValue(acos(popFromValue())); break;
                        case eFunction_arctan:  pushToValue(atan(popFromValue())); break;
                        case eFunction_fabs:    pushToValue(fabs(popFromValue())); break;
                        case eFunction_ln:      pushToValue(log(popFromValue())); break;
                        case eFunction_log:     pushToValue(log10(popFromValue())); break;
                    }
                    break;

                case eOperation_op:
                    switch (op.op)
                    {
                        case '+' : op2 = popFromValue(); pushToValue(popFromValue() + op2); break;
                        case '-' : op2 = popFromValue(); pushToValue(popFromValue() - op2); break;
                        case '*' : op2 = popFromValue(); pushToValue(popFromValue() * op2); break;
                        case '/' : op2 = popFromValue(); pushToValue(popFromValue() / op2); break;
                        case '%' : op2 = popFromValue(); pushToValue((double)((int)popFromValue() % (int)op2)); break;
                        case '^' : op2 = popFromValue(); pushToValue(pow(popFromValue(), op2));break;
                        case '|' : pushToValue(fabs(popFromValue())); break;
                        case '=' : result = popFromValue(); return true;
                    }
                    break;
                
                default:
                    println(DEBUG, "[Error]: Unknown command [ ", op.opType, "].");
                    return false;
            }
            printDeque("count");
        }
        println(DEBUG, "Count error !!");
        return false;
    }

private:

    bool _flagLastIsNumber = false;
    double _lastValue = 0;

    std::string _strFormula;

    std::deque<char>        _buffer;
    std::deque<sOperation>  _suffix;
    std::deque<sOperation>  _stack;
    std::deque<double>      _value;

    void printDeque(std::string str)
    {
        #ifdef TEST
        println("------------------------------------");
        println(str);
        println("_buffer : ", _buffer);
        println("_suffix : ", _suffix);
        println("_stack  : ", _stack);
        println("_value  : ", _value);
        #endif
    }

    // 把f压入到值栈中
    void pushToValue(double f)
    {
        _value.emplace_back(f);
    }

    // 弹出并返回栈顶的值
    double popFromValue(void) 
    {
        if(!_value.empty()){
            double top = _value.back();
            _value.pop_back();
            return top;
        }
        else{
            println(DEBUG, _value.size(), " stack '_value' is empty!");
            return 0.0;
        }
    }

    // 计算小数位数
    size_t digits(double num)
    {
        int a, n = 0;
        const double b = 1e-6;
        
        a = num;
        num = num - a;
        while((b < num && num < 1 - b) || (b - 1 < num && num < -b)){
            num = num * 10;
            a = num;
            num = num - a;
            n++;
        }
        return n;
    }

    int operateLevel(sOperation op)
    {
        if (op.opType == eOperation_op)
        {
            switch(op.op)
            {
                case '(' : return 0;
                case ')' : return 0;
                case '+' : return 1;
                case '-' : return 1;
                case '*' : return 2;
                case '/' : return 2;
                case '%' : return 2;
                case '^' : return 3;
                case '|' : return 3;
                default  : return MYERROR;
            }
        }
        else
        {
            switch(op.funcType)
            {
                case eFunction_sqrt:    return 3;
                case eFunction_fabs:    return 3;
                case eFunction_sin:     return 3;
                case eFunction_cos:     return 3;
                case eFunction_tan:     return 3;
                case eFunction_sinh:    return 3;
                case eFunction_cosh:    return 3;
                case eFunction_tanh:    return 3;
                case eFunction_arcsin:  return 3;
                case eFunction_arccos:  return 3;
                case eFunction_arctan:  return 3;
                case eFunction_ln:      return 3;
                case eFunction_log:     return 3;
                default:                return MYERROR;
            }
        }
        return MYERROR;
    }

    char getop(std::string &str, char c)
    {
        int i = 0;
        char type = 0;

        str[i++] = c;               // 持续检测下一个字符，直到下一个字符是回车或者不是字母
        while (!_buffer.empty())
        {
            type = _buffer.front();
            _buffer.pop_front();
            if (type == '\n' || !isalpha(type)) {
                break;
            }
            str[i++] = type;
            if (type == '(') {      // 检测到左括号(，停止检测
                i++;
                break;
            }
        }
        str[i] = '\0';
        if (i < OPLEN_MAX) {        // 操作得到的string运算符一般小于8个字节
            if (type != '\n') {     // 如果下一个字符不是回车结束符，那么把这个字符重新返回到输入流中
                _buffer.push_front(type);
            }
            return 0;
        }
        return MYERROR;             // 如果i == OPLEN_MAX，就返回错误值-1
    }

    // 匹配运算符
    struct operation
    {
        std::string     word;   // 运算符字符串
        int             time;   // 出现次数
        eFunctionType   func;   // 运算符值（单字符）
    };

    // 在字符串集中中搜索匹配word字符串的字符串，返回找到的字符串集的下标，ops为字符串的长度
    char binSearch(std::string &str, struct operation operate[], int ops)  
    {
        int cond;
        int low, high, mid;

        low = 0;
        high = ops - 1;

        while (low <= high) {
            mid = (low + high) / 2;
            if ((cond = strcmp(str.c_str(), operate[mid].word.c_str())) < 0) {
                high = mid - 1;
            }
            else if (cond > 0) {
                low = mid + 1;
            }
            else {
                return mid;
            }
        }
        return MYERROR;
    }

    eFunctionType mathOperate(char c)
    {
        struct operation operate[] = { //按ascll码顺序从小到大排放
            {"ARCCOS", 0, eFunction_arccos},
            {"ARCSIN", 0, eFunction_arcsin},
            {"ARCTAN", 0, eFunction_arctan},
            {"COSH", 0, eFunction_cosh},
            {"COS" , 0, eFunction_cos},
            {"FABS", 0, eFunction_fabs},
            {"LN"  , 0, eFunction_ln},
            {"LOG" , 0, eFunction_log},
            {"SINH", 0, eFunction_sinh},
            {"SIN" , 0, eFunction_sin},
            {"SQRT", 0, eFunction_sqrt},
            {"TANH", 0, eFunction_tanh},
            {"TAN" , 0, eFunction_tan},

            {"arccos", 0, eFunction_arccos},
            {"arcsin", 0, eFunction_arcsin},
            {"arctan", 0, eFunction_arctan},
            {"cosh", 0, eFunction_cosh},
            {"cos" , 0, eFunction_cos},
            {"fabs", 0, eFunction_fabs},
            {"ln"  , 0, eFunction_ln},
            {"log" , 0, eFunction_log},
            {"sinh", 0, eFunction_sinh},
            {"sin" , 0, eFunction_sin},
            {"sqrt", 0, eFunction_sqrt},
            {"tanh", 0, eFunction_tanh},
            {"tan" , 0, eFunction_tan},
        };
        std::string str;
        int find;
        int ops = (int)(sizeof(operate) / sizeof(struct operation)); // 字符串个个数

        getop(str, c);
        if ((find = binSearch(str, operate, ops)) != MYERROR)
        {
            operate[find].time++;           // 运算符出现的次数++
            return operate[find].func;        // 返回运算符（单字符）
        }
        return eFunction_invalid;
    }

    char getOperation(sOperation &op)
    {
        char c = 0;

        if (_buffer.empty())
        {
            return false;
        }

        while (!_buffer.empty()) {
            c = _buffer.front();
            _buffer.pop_front();
            if (c != ' ' && c != '\t') { // 跳过所有的空格
                break;
            }
        }

        if (!isdigit(c) && c != '.') 
        {
            /* op or function */
            if (_flagLastIsNumber) { // 上一个值是数字，但是下一个是运算符，两者之间没有乘，自动添加一个
                #ifdef TEST
                println(DEBUG, c);
                #endif
                if (c == '('
                    || c == 'f' || c == 's' || c == 'c' || c == 't' || c == 'l' || c == 'a'
                    || c == 'F' || c == 'S' || c == 'C' || c == 'T' || c == 'L' || c == 'A'
                    || c == 'p' || c == 'P'
                    || c == 'e' || c == 'E') {
                    _buffer.emplace_front(c);
                    _flagLastIsNumber = false;
                    op.opType = eOperation_op;
                    op.op = '*';
                    return true;
                }
            }
            else {
                #ifdef TEST
                println(DEBUG, c);
                #endif
                if (c == '-') {
                    /* */
                }
                else if (c == 'f' || c == 's' || c == 'c' || c == 't' || c == 'l' || c == 'a'
                    || c == 'F' || c == 'S' || c == 'C' || c == 'T' || c == 'L' || c == 'A') {
                    _flagLastIsNumber = false;
                    op.opType = eOperation_func;
                    op.funcType = mathOperate(c);
                    return true;
                }
                else if (c == 'p' || c == 'P') {//  是pi = PI = 3.1415926, e = 2.7
                    _flagLastIsNumber = true;
                    op.opType = eOperation_numDouble;
                    op.numDouble = PI;
                    return true;
                }
                else if (c == 'e' || c == 'E') {
                    _flagLastIsNumber = true;
                    op.opType = eOperation_numDouble;
                    op.numDouble = E;
                    return true;
                }
            }
            if (c == '(' || c == ')' || c == '+' || c == '-' || c == '*' || c == '/' || c == '%' || c == '^' || c == '|' ) {
                _flagLastIsNumber = false;
                op.opType = eOperation_op;
                op.op = c;
                return true;
            }
            return false;
        }
        else{
            #ifdef TEST
            println(DEBUG, c);
            #endif

            bool bDouble = false;
            int index = 0;
            std::string number;

            number[index++] = c;
            if (isdigit(c)) {
                while (!_buffer.empty()) { // 收集整数部分
                    number[index++] = c = _buffer.front();
                    _buffer.pop_front();
                    if (!isdigit(c)) {
                        _buffer.push_front(c);
                        break;
                    }
                }
            }
            if (c == '.') {
                while (!_buffer.empty()) { // 收集小数部分
                    number[index++] = c = _buffer.front();
                    _buffer.pop_front();
                    if (!isdigit(c)) {
                        _buffer.push_front(c);
                        break;
                    }
                }
                bDouble = true;
            }
            number[index++] = '\0';
            _flagLastIsNumber = true;
            if (bDouble)
            {
                op.opType = eOperation_numDouble;
                op.numDouble = atof(number.c_str());
            }
            else
            {
                op.opType = eOperation_numInt;
                op.numInt = atoi(number.c_str());
            }
            return true;
        }
    }

    void convertFormula2Buffer(void)
    {
        int len = _strFormula.size();

        for (int i = 0; i < len; i++) {
            _buffer.emplace_back(_strFormula[i]);
        }
    }

    void convertBuffer2Suffix(void)
    {
        sOperation op;
        sOperation opTemp;
        int level = 0;
        int lastLevel = 0; //运算等级

        while (getOperation(op)) 
        {
            #ifdef TEST
            op.print();
            #endif

            switch (op.opType)
            {
                case eOperation_numInt:
                case eOperation_numDouble:
                    _suffix.emplace_back(op);
                    break;

                case eOperation_op:
                    if (op.op == '(')
                    {
                        lastLevel = operateLevel(op);
                        _stack.emplace_back(op);
                        break;
                    }
                    else if (op.op == ')')
                    {
                        if(!_stack.empty()){
                            opTemp = _stack.back();
                            _stack.pop_back();
                            while (operateLevel(opTemp) > 0) {
                                _suffix.emplace_back(opTemp);
                                if(!_stack.empty()){
                                    opTemp = _stack.back();
                                    _stack.pop_back();
                                }
                                else{
                                    break;
                                }
                            }
                        }
                        if(!_stack.empty()){
                            opTemp = _stack.back();             // 得到'('前一个运算符的运算等级
                            lastLevel = operateLevel(opTemp);   // 记录为上一次运算等级
                        }
                        else{
                            lastLevel = operateLevel(opTemp);
                        }
                        break;
                    }
                    // break; /* 此处不需要*/

                case eOperation_func:
                    level = operateLevel(op);
                    if (level > lastLevel) {
                        _stack.emplace_back(op);
                    }
                    else {
                        if(!_stack.empty()){
                            opTemp = _stack.back();
                            _stack.pop_back();
                            while (level <= operateLevel(opTemp)) {
                                _suffix.emplace_back(opTemp);
                                if(!_stack.empty()){
                                    opTemp = _stack.back();
                                    _stack.pop_back();
                                }
                                else{
                                    break;
                                }
                            }
                        }
                        _stack.emplace_back(op);
                    }
                    lastLevel = level;
                    break;

                default:
                    println(DEBUG, "[Error]: Unknown command [ ", op.opType, " ]");
                    break;
            }
        }

        while (!_stack.empty()) {
            _suffix.emplace_back(_stack.back());
            _stack.pop_back();
        }

        op.opType = eOperation_op;
        op.op = '=';
        _suffix.emplace_back(op);
    }
};

/******************************************************************************
    Calculator
******************************************************************************/

Calculator::Calculator()
    : _pimpl(new impl)
{
}

Calculator::~Calculator()
{
}

void Calculator::setFormula(std::string &str)
{
    _pimpl->setFormula(str);
}

bool Calculator::count(double &result)
{
    if (!_pimpl) {
        return false;
    }
    return _pimpl->count(result);
}
